package datastructure.linkedlist;

/**
 * 1、添加元素
 * 2、使用虚拟头结点
 * 3、遍历查询修改
 * 4、删除
 * 5、实现栈
 * 6、尾指针链表
 */
public class LinkedList<E> {
    private Node dummyHead;
    private int size;

    public LinkedList() {
        dummyHead = new Node();
    }

    public LinkedList(int size) {

    }

    public int getSize() {
        return size;
    }


    public boolean isEmpty(){
        return size == 0;
    }

    // 任意位置添加
    public void addNode(int index, E e) {
        if (index > size || index < 0) {
            throw new IllegalArgumentException("position is illegal");
        }
        Node prev = dummyHead;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }
        prev.next = new Node(e, prev.next);
        size++;
    }

    // 在头部添加
    public void addFirst(E e) {
        addNode(0, e);
    }

    public void addLast(E e) {
        addNode(size, e);
    }

    public void setElement(int index, E e){
        if (index < 0|| index > size) {
            throw new IllegalArgumentException("position is illegal");
        }
        Node cur = dummyHead.next;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        cur.element = e;
    }

    public E removeElement(int index){
        if (index < 0|| index > size) {
            throw new IllegalArgumentException("position is illegal");
        }
        Node prev = dummyHead;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }
        Node cur = prev.next;
        prev.next = cur.next;
        cur.next = null;
        size--;
        return cur.element;
    }
    public E removeFirst(){
        return removeElement(0);
    }
    public void removeLast(){
        removeElement(size);
    }

    public E get(int index){
        if (index < 0|| index > size) {
            throw new IllegalArgumentException("position is illegal");
        }
        Node cur = dummyHead.next;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        return cur.element;
    }

    public E getFirst(){
        return get(0);
    }
    public E getLast(){
        return get(size);
    }
    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder("head->");
        Node cur = dummyHead.next;
        while (cur != null) {
            stringBuilder.append(cur.element).append("->");
            cur = cur.next;
        }
        stringBuilder.append("NULL");
        return stringBuilder.toString();
    }

    public void revert() {
        // 三指针法翻转链表

    }

    private class Node {
        /**
         * 1、链表元素，一个结点，一个next
         */
        public E element;
        public Node next;

        // 2、构造函数
        public Node(E e, Node next) {
            this.element = e;
            this.next = next;
        }

        public Node(E e) {
            this(e, null);
        }

        public Node() {
            this(null, null);
        }

        @Override
        public String toString() {
            return "Node{" +
                    "element=" + element +
                    ", next=" + next +
                    '}';
        }
    }
}
